package cn.njupt.unionfind;
//快速合并
public class Quick_Union extends Union_Find {


    public Quick_Union(int capacity) {
        super(capacity);
    }

    /**
     * 找到当前节点的代表元素，也就是最祖先节点
     * @param child
     * @return
     */
    @Override
    public int find(int child) {
        rangCheck(child);
        while(child!=parent[child]){
            child=parent[child];
        }
        return child;
    }

    @Override
    public void union(int child1, int child2) {
        //左边为子节点，右边为父节点
        int p1=find(child1);
        int p2=find(child2);
        if(p1==p2)return;
        parent[p1]=p2;
    }
}
